﻿using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Windows;
using System.Windows.Controls;
using System.Windows.Shapes;
using System.Windows.Media;

namespace FourPartHarmony3
{
    public class HorizontalTree<T> where T : class {
        Rect mBounds;
        QuadrantHorizontal mRoot;
        IDictionary<T, QuadrantHorizontal> mTable;

        #region HorizontalNode implementation
        /// <summary>
        /// NodeとそのNodeのBounds、HorizontalNodeのサーキュラーリストを手繰るNext。
        /// </summary>
        internal class HorizontalNode {
            Rect mBounds;
            HorizontalNode mNext; // linked in a circular list.
            T mNode; // the actual visual object being stored here.

            /// <param name="node">The node</param>
            /// <param name="bounds">The bounds of that node</param>
            public HorizontalNode(T node, Rect bounds) {
                mNode   = node;
                mBounds = bounds;
            }

            public T Node {
                get { return mNode; }
                set { mNode = value; }
            }

            public Rect Bounds {
                get { return mBounds; }
            }

            public HorizontalNode Next {
                get { return mNext; }
                set { mNext = value; }
            }
        }
        #endregion // HorizontalNode implementation

        #region QuadrantHorizontal implementation

        /// <summary>
        /// 左右に2分割された2つの象限。
        /// </summary>
        internal class QuadrantHorizontal {
            QuadrantHorizontal mParent;
            Rect mBounds;

            /// <summary>
            /// mBoundsの左右にまたがって存在するNodeのリスト。
            /// </summary>
            HorizontalNode mNodes;

            /// <summary>
            /// mBoundsの左半分に完全に内包されるNodeのリスト。
            /// </summary>
            QuadrantHorizontal mLeft;

            /// <summary>
            /// mBoundsの右半分に完全に内包されるNodeのリスト。
            /// </summary>
            QuadrantHorizontal mRight;

            public QuadrantHorizontal(QuadrantHorizontal parent, Rect bounds) {
                mParent = parent;
                mBounds = bounds;
            }

            internal QuadrantHorizontal Parent {
                get { return mParent; }
            }

            internal Rect Bounds { 
                get { return mBounds; } 
            }

            internal QuadrantHorizontal Insert(T node, Rect bounds) {
                if (bounds.Width == 0 || bounds.Height == 0) {
                    throw new ArgumentException("Bounds of QuadrantHorizontal cannot be zero width or height");
                }

                double wHalf = mBounds.Width / 2;
                if (wHalf == 0) {
                    wHalf = 1;
                }
                double h = mBounds.Height;

                Rect left  = new Rect(mBounds.Left,         mBounds.Top, wHalf, h);
                Rect right = new Rect(mBounds.Left + wHalf, mBounds.Top, wHalf, h);

                QuadrantHorizontal child = null;

                if (left.Contains(bounds)) {
                    if ( mLeft == null) {
                        mLeft = new QuadrantHorizontal(this, left);
                    }
                    child = mLeft;
                } else if (right.Contains(bounds)) {
                    if ( mRight == null) {
                        mRight = new QuadrantHorizontal(this, right);
                    }
                    child = mRight;
                }

                if (child != null) {
                    return child.Insert(node, bounds);
                } else {
                    // 左半分も右半分にも含まれないので、左右にまたがって存在する。

                    HorizontalNode n = new HorizontalNode(node, bounds);
                    if (mNodes == null) {
                        // 1個目。
                        n.Next = n;
                    } else {
                        // サーキュラーリストの先頭にnを追加。
                        HorizontalNode x = mNodes;
                        n.Next = x.Next;
                        x.Next = n;
                    }
                    mNodes = n;
                    return this;
                }
            }
            
            /// <summary>
            /// boundsに交差するすべてのNodeを戻す。
            /// </summary>
            /// <param name="bounds">[in] The bounds that contains the nodes you want returned</param>
            internal IEnumerable<HorizontalNode> GetIntersectingNodes(Rect bounds) {
                if (bounds.IsEmpty) {
                    yield break;
                }

                double wHalf = mBounds.Width / 2;
                if (wHalf == 0) {
                    wHalf = 1;
                }
                double h = mBounds.Height;

                Rect left  = new Rect(mBounds.Left,         mBounds.Top, wHalf, h);
                Rect right = new Rect(mBounds.Left + wHalf, mBounds.Top, wHalf, h);

                if (left.IntersectsWith(bounds) && mLeft != null) {
                    foreach (var node in mLeft.GetIntersectingNodes(bounds)) {
                        yield return node;
                    }
                }

                if (right.IntersectsWith(bounds) && mRight != null) {
                    foreach (var node in mRight.GetIntersectingNodes(bounds)) {
                        yield return node;
                    }
                }

                foreach (var node in GetIntersectingNodes(mNodes, bounds)) {
                    yield return node;
                }
            }

            static IEnumerable<HorizontalNode> GetIntersectingNodes(HorizontalNode last, Rect bounds) {
                if (last == null) {
                    yield break;
                }
                HorizontalNode n = last;
                do {
                    n = n.Next;
                    if (n.Bounds.IntersectsWith(bounds)) {
                        yield return n;
                    }
                } while (n != last);
            }

            /// <summary>
            /// Return true if there are any nodes in this QuadrantHorizontal that intersect the given bounds.
            /// </summary>
            /// <param name="bounds">The bounds to test</param>
            /// <returns>boolean</returns>
            internal bool HasIntersectingNodes(Rect bounds) {
                if (bounds.IsEmpty) {
                    return false;
                }

                double wHalf = mBounds.Width / 2;
                double h     = mBounds.Height;

                Rect left  = new Rect(mBounds.Left,         mBounds.Top, wHalf, h);
                Rect right = new Rect(mBounds.Left + wHalf, mBounds.Top, wHalf, h);

                if (left.IntersectsWith(bounds) && mLeft != null) {
                    if (mLeft.HasIntersectingNodes(bounds)) {
                        return true;
                    }
                }

                if (right.IntersectsWith(bounds) && mRight != null) {
                    if (mRight.HasIntersectingNodes(bounds)) {
                        return true;
                    }
                }

                return HasIntersectingNodes(mNodes, bounds);
            }

            /// <summary>
            /// Walk the given linked list and test each node against the given bounds/
            /// </summary>
            /// <param name="last">The last node in the circularly linked list.</param>
            /// <param name="bounds">Bounds to test</param>
            /// <returns>Return true if a node in the list intersects the bounds</returns>
            static bool HasIntersectingNodes(HorizontalNode last, Rect bounds) {
                if (last != null) {
                    HorizontalNode n = last;
                    do {
                        n = n.Next; // first node.
                        if (n.Bounds.IntersectsWith(bounds)) {
                            return true;
                        }
                    } while (n != last);
                }
                return false;
            }

            /// <summary>
            /// Remove the given node from this QuadrantHorizontal.
            /// </summary>
            /// <param name="node">The node to remove</param>
            /// <returns>Returns true if the node was found and removed.</returns>
            internal bool RemoveNode(T node) {
                if (mNodes == null) {
                    return false;
                }

                HorizontalNode p = mNodes;
                while (p.Next.Node != node && p.Next != mNodes) {
                    p = p.Next;
                }
                if (p.Next.Node != node) {
                    return false;
                }

                HorizontalNode n = p.Next;
                if (p == n) {
                    // 1個→0個
                    mNodes = null;
                } else {
                    if (mNodes == n) mNodes = p;
                    p.Next = n.Next;
                }
                return true;
            }
        }
#endregion // QuadrantHorizontal

        public HorizontalTree(Rect bounds) {
            mBounds = bounds;
            mRoot = new QuadrantHorizontal(null, mBounds);
            mTable = new Dictionary<T, QuadrantHorizontal>();
        }

        public Rect Bounds {
            get { return mBounds; }
        }

        /// <summary>
        /// Boundsを更新する。非常に重い。
        /// </summary>
        public void ChangeBounds(Rect bounds) {
            mBounds = bounds;
            ReIndex();
        }

        /// <summary>
        /// Insert a node with given bounds into this HorizontalTree.
        /// </summary>
        /// <param name="node">The node to insert</param>
        /// <param name="bounds">The bounds of this node</param>
        public void Insert(T node, Rect bounds) {
            if (mBounds.Width == 0 || mBounds.Height == 0) {
                throw new InvalidOperationException("You must set a non-zero bounds on the HorizontalTree first");
            }
            if (bounds.Width == 0 || bounds.Height == 0) {
                throw new InvalidOperationException("Inserted node must have a non-zero width and height");
            } 

            QuadrantHorizontal parent = mRoot.Insert(node, bounds);

            mTable[node] = parent;
        }

        /// <summary>
        /// Get a list of the nodes that intersect the given bounds.
        /// </summary>
        /// <param name="bounds">The bounds to test</param>
        /// <returns>List of zero or mode nodes found inside the given bounds</returns>
        public IEnumerable<T> GetNodesInside(Rect bounds) {
            foreach (HorizontalNode n in GetNodes(bounds)) {
                yield return n.Node;
            }
        }

        /// <summary>
        /// Get a list of the nodes that intersect the given bounds.
        /// </summary>
        /// <param name="bounds">The bounds to test</param>
        /// <returns>List of zero or mode nodes found inside the given bounds</returns>
        public bool HasNodesInside(Rect bounds) {
            return mRoot.HasIntersectingNodes(bounds);
        }

        /// <summary>
        /// Get list of nodes that intersect the given bounds.
        /// </summary>
        /// <param name="bounds">The bounds to test</param>
        /// <returns>The list of nodes intersecting the given bounds</returns>
        IEnumerable<HorizontalNode> GetNodes(Rect bounds) {
            foreach (var node in mRoot.GetIntersectingNodes(bounds)) {
                yield return node;
            }
        }

        /// <summary>
        /// Remove the given node from this HorizontalTree.
        /// </summary>
        /// <param name="node">The node to remove</param>
        /// <returns>True if the node was found and removed.</returns>
        public bool Remove(T node) {
            QuadrantHorizontal parent = null;
            if (!mTable.TryGetValue(node, out parent)) {
                return false;
            }
            parent.RemoveNode(node);
            mTable.Remove(node);
            return true;
        }

        /// <summary>
        /// Rebuild all the Quadrants according to the current HorizontalTree Bounds.
        /// </summary>
        void ReIndex() {
            mRoot = new QuadrantHorizontal(null, mBounds);
            foreach (HorizontalNode n in GetNodes(mBounds)) {
                Insert(n.Node, n.Bounds);
            }
        }
    }
}
